package beans.dao;

public class test {

    public static void main(String[] args) {
        int[] nums = {3,2,3,1,2,4,5,5,6};
        int k = 4;
        int result = findKthLargest(nums, k);
        System.out.println("The " + k + "th largest number is: " + result);
    }

    public static int findKthLargest(int[] nums, int k) {
        int n=nums.length;
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == n-k) {
                return nums[pivotIndex];
            } else if (pivotIndex < n-k) {
                left = pivotIndex + 1;
            } else {
                right = pivotIndex - 1;
            }
        }

        throw new IllegalArgumentException("Invalid input");
    }

    private static int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = r - 1;

        for (int j = i; j >= l; j--) {
            if (nums[j] >= pivot) {
                swap(nums, i, j);
                i--;
            }
        }

        swap(nums, i + 1, r);
        return i + 1;
    }

    private static void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}

